package com.xie.sort.gnomesort;

import java.util.Arrays;

/**
 * 地精排序(Gnome Sort)——最简单的排序算法
 */
public class gnomeSort {

    public static void main(String[] args) {
        int[] arr = {49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22};
        // 原始算法
        gnomeSort1(arr);

        arr = new int[]{49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22};
        // 尝试优化
        gnomeSort2(arr);
    }

    static void gnomeSort1(int[] nums) {
        System.out.println("--------------------gnomeSort1---------------------");
        int length = nums.length;
        int i = 0;
        int num = 0;
        while (i < length) {
//            if (i > 0 && nums[i - 1] >= nums[i]) {
            if (i > 0 && nums[i - 1] > nums[i]) {
                //交换
                swap(nums, i - 1, i);
                i--;
            } else {
                i++;
            }
            System.out.print("第" + ++num + "次循环:");
            System.out.println(Arrays.toString(nums));
        }
    }

    static void gnomeSort2(int[] nums) {
        System.out.println("--------------------gnomeSort2---------------------");
        int length = nums.length;
        // 直接从第二个开始
        int i = 1;
        int num = 0;
        int position = -1;
        while (i < length) {
            if (i > 0 && nums[i - 1] > nums[i]) {
                //记录位置
                if (position == -1) {
                    position = i;
                }
                //交换
                swap(nums, i - 1, i);
                i--;
            } else {
                if (position == -1) {
                    i++;
                } else {
                    //跳到 记录位置 + 1
                    i = position + 1;
                    position = -1;
                }
            }
            System.out.print("第" + ++num + "次循环:");
            System.out.println(Arrays.toString(nums));
        }
    }

    /**
     * 交换位置
     *
     * @param nums
     * @param start
     * @param end
     */
    private static void swap(int[] nums, int start, int end) {
        int temp;
        temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
    }
}
